package com.leetcode.algorithm.y22.m06;

/**
 * 441. 排列硬币
 * 
 * https://leetcode.cn/problems/arranging-coins/
 * 
 * @author jie.deng
 *
 */
class Question0441Solution01 {
	
	public int arrangeCoins(int n) {
		// 大于等于(1+i)*i/2 && 小于 (1+i)*(i+2)/2
		int left = 1;
		int right = n;
		// [left,...i...,right)
		while (left < right) {
			int mid = left + ((right - left + 1) >> 1);
			long sum = (long) mid * (mid + 1) / 2;
			if (sum == n) {
				return mid;
			} else if (sum < n) {
				left = mid;
			} else {
				right = mid - 1;
			}
		}

		return right;
	}
    
}